package com.test.gpa.test.suanfa;

import io.netty.util.internal.StringUtil;
import org.apache.commons.lang3.StringUtils;


import java.sql.Connection;
import java.util.*;
import java.util.stream.Collectors;


import static org.hibernate.query.criteria.internal.ValueHandlerFactory.isNumeric;

public class offer {
//    public static void main(String[] args) {
//        System.gc();
//        final int[] a = new int[]{1, 2, 3, 4};
//        System.out.println(a);
//        a[0] = 9;
//        System.out.println(a + "  " + a[0]);
//        checkInclusion("ab", "kkkkcbawww");
//        lengthOfLongestSubstring("ooooooooooooooooo");
//        offer offer = new offer();
//        String[] strings = new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
//        offer.evalRPN(strings);
//        offer.asteroidCollision(new int[]{10, 2, -5});
//        Deque<Integer> deque = new LinkedList<>();

//        deque.push(1);
//        deque.push(2);
//        deque.push(3);
//        deque.push(4);
//        deque.add(1);
//        deque.add(2);
//        deque.add(3);
//        deque.add(4);
//        deque.addFirst(5);
//        Integer peek = deque.peekLast();
//        Integer poll = deque.pollLast();
//        System.out.println(peek);
//        Integer peek1 = deque.peek();
//        System.out.println(peek1);
//        Integer poll = deque.poll();
//        System.out.println(poll);
//        Integer integer = deque.peekFirst();
//        System.out.println(integer);
//        Integer integer1 = deque.pollFirst();
//        System.out.println(integer1);
//        Integer integer2 = deque.pollLast();
//        System.out.println(integer2);
//        Queue<Integer> queue=new ArrayDeque<>();
//        queue.add()
//        System.out.println(poll);
//    }

    class Solution {
        public int findMaxLength(int[] nums) {
            int maxLength = 0;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            int counter = 0;
            map.put(counter, -1);
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                int num = nums[i];
                if (num == 1) {
                    counter++;
                } else {
                    counter--;
                }
                if (map.containsKey(counter)) {
                    int prevIndex = map.get(counter);
                    maxLength = Math.max(maxLength, i - prevIndex);
                } else {
                    map.put(counter, i);
                }
            }
            return maxLength;
        }
    }

    public int pivotIndex(int[] nums) {

        int numsSum = 0;
        for (int i = 0; i < nums.length; i++) {
            numsSum += nums[i];
        }
        int a = -1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {

            if (count == numsSum - count - nums[i]) {
                a = i;
                return a;
            }
            count += nums[i];
        }
        return a;

    }

    class NumMatrix {
        private int[][] ma;

        public NumMatrix(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            ma = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    ma[i + 1][j + 1] = ma[i + 1][j] + ma[i][j + 1] - ma[i][j] + matrix[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {

            int num = ma[row2 + 1][col2 + 1] - ma[row1][col2 + 1] - ma[row2 + 1][col1] + ma[row1][col1];
            return num;
        }
    }

    public static boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int[] s1nums = new int[26];
        int[] s2nums = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            ++s1nums[s1.charAt(i) - 'a'];
            ++s2nums[s2.charAt(i) - 'a'];
        }
        if (Arrays.equals(s1nums, s2nums)) return true;
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            --s2nums[s2.charAt(i) - 'a'];
            ++s2nums[s2.charAt(i + s1.length()) - 'a'];
            if (Arrays.equals(s1nums, s2nums)) return true;
        }

        return false;
    }

    public List<Integer> findAnagrams(String s, String p) {
        String s2 = s;
        String s1 = p;
        List<Integer> list = new ArrayList<>();
        if (s1.length() > s2.length()) return list;
        int[] s1nums = new int[26];
        int[] s2nums = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            ++s1nums[s1.charAt(i) - 'a'];
            ++s2nums[s2.charAt(i) - 'a'];
        }
        if (Arrays.equals(s1nums, s2nums)) list.add(0);
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            --s2nums[s2.charAt(i) - 'a'];
            ++s2nums[s2.charAt(i + s1.length()) - 'a'];
            if (Arrays.equals(s1nums, s2nums)) list.add(i + 1);
        }
        return list;
    }

    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int end = 0;
        int lengthMax = 0;
        for (int start = 0; start < s.length(); start++) {
            if (start != 0) set.remove(s.charAt(start - 1));
            while (end < s.length() && !set.contains(s.charAt(end))) {
                set.add(s.charAt(end));
                end++;
            }
            lengthMax = Math.max(lengthMax, end - start);
        }
        return lengthMax;
    }


    public boolean validPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start <= end) {
            if (s.charAt(start) != s.charAt(end)) {
                return valid(s, start, end - 1) || valid(s, start + 1, end);

            }
            start++;
            end--;


        }
        return true;

    }

    public boolean valid(String s, int low, int high) {
        while (low <= high) {
            if (s.charAt(low) != s.charAt(high)) {
                return false;
            }
            low++;
            high--;
        }
        return true;

    }


    public int countSubstrings(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }


    public static ListNode removeNthFromEnd(ListNode head, int n) {
        int sum = 0;
        ListNode y = new ListNode();
        y.next = head;
        ListNode first = y;
        while (first != null) {
            sum++;
            first = first.next;
        }
        ListNode listNode = y;
        int i = sum - n;
        while (true) {
            if (i == 1) {
                listNode.next = listNode.next.next;
                return y.next;

            }
            i--;
            listNode = listNode.next;
        }
    }

    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet();
        ListNode listNode = head;
        while (listNode != null) {
            if (!set.add(listNode)) {
                return listNode;
            }
            listNode = listNode.next;

        }
        return null;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode listNodeA = headA;
        ListNode listNodeB = headB;
        while (listNodeA != null) {
            set.add(listNodeA);
            listNodeA = listNodeA.next;
        }
        while (listNodeB != null) {

            if (!set.add(listNodeB)) {
                return listNodeB;
            }
            listNodeB = listNodeB.next;
        }
        return null;
    }

    public ListNode reverseList(ListNode head) {
        ListNode first = head;
        ListNode L = null;
        while (first != null) {
            ListNode node = first.next;
            first.next = L;
            L = first;
            first = node;
        }
        return L;
    }


    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<ListNode> listNodeL1 = new ArrayDeque<>();
        Deque<ListNode> listNodeL2 = new ArrayDeque<>();
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                listNodeL1.push(l1);
                l1 = l1.next;
            }
            if (l2 != null) {
                listNodeL2.push(l2);
                l2 = l2.next;
            }
        }

        ListNode listNode1 = null;
        int count = 0;
        for (; !listNodeL1.isEmpty() || !listNodeL2.isEmpty(); ) {
            int first = listNodeL1.isEmpty() ? 0 : listNodeL1.pop().val;
            int second = listNodeL2.isEmpty() ? 0 : listNodeL2.pop().val;
            int sum = (first + second + count) % 10;
            count = (first + second + count) / 10;
            ListNode listNode = new ListNode(sum, listNode1);
            listNode1 = listNode;
        }
        return count == 0 ? listNode1 : new ListNode(count, listNode1);
    }

    public void reorderList(ListNode head) {
        int len = 0;
        ListNode listNode = head;
        while (head != null) {
            len++;
            head = head.next;
        }
        ListNode[] listNodes = new ListNode[len];
        for (int i = 0; i < len && listNode != null; i++) {
            listNodes[i] = listNode;
            listNode = listNode.next;
        }
        int i = 0;
        int j = len - i - 1;
        while (i < j) {
            listNodes[i].next = listNodes[j];
            i++;
            if (i == j) break;
            listNodes[j].next = listNodes[i];
            j--;
        }
        listNodes[i].next = null;
    }

    public ListNode listNodeReorder(ListNode listNode) {

        ListNode listNode1 = null;
        while (listNode != null) {
            ListNode listNode2 = listNode.next;
            listNode.next = listNode1;
            listNode1 = listNode;
            listNode = listNode2;
        }
        return listNode1;
    }

    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode listNode = head;
        while (head != null) {
            len++;
            head = head.next;
        }
        ListNode[] listNodes = new ListNode[len];
        for (int i = 0; i < len && listNode != null; i++) {
            listNodes[i] = listNode;
            listNode = listNode.next;
        }
        int start = 0;
        int end = len - 1;
        while (start < end) {
            if (listNodes[start].val != listNodes[end].val) return false;
            start++;
            end--;
        }
        return true;

    }

    public int findMinDifference(List<String> timePoints) {
        int min = Integer.MAX_VALUE;

        Collections.sort(timePoints);
        for (int i = 0; i < timePoints.size() - 1; i++) {
            int time = getTime(timePoints.get(i)) - getTime(timePoints.get(i + 1));
            min = Math.min(Math.abs(time), min);
        }
        min = Math.min(min, 24 * 60 + getTime(timePoints.get(0)) - getTime(timePoints.get(timePoints.size() - 1)));
        return min;

    }

    public int getTime(String str) {

        return ((str.charAt(0) - '0') * 10 + str.charAt(1) - '0') * 60 + (str.charAt(3) - '0') * 10 + str.charAt(4) - '0';
    }

    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (isChar(s)) {
                int num1 = deque.pop();
                int num2 = deque.pop();
                deque.push(add(num2, num1, s.charAt(0)));

            } else {
                deque.push(Integer.valueOf(s));
            }
        }

        return deque.pop();
    }

    public Integer add(Integer a, Integer b, char c) {
        if (c == '+') {
            return a + b;
        } else if (c == '-') {
            return a - b;
        } else if (c == '*') {
            return a * b;

        } else if (c == '/') {
            return a / b;
        }
        return 0;
    }

    public boolean isChar(String c) {
        if (c.equals("+")) {
            return true;
        } else if (c.equals("-")) {
            return true;
        } else if (c.equals("*")) {
            return true;

        } else if (c.equals("/")) {
            return true;
        }
        return false;
    }

    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> deque = new LinkedList<>();
        for (int num2 :
                asteroids) {
            recursion(deque, num2);
        }
        int[] ints = new int[deque.size()];
        for (int i = 0; !deque.isEmpty(); i++) {
            ints[i] = deque.pollLast();
        }
        return ints;
    }

    public void recursion(Deque<Integer> deque, int num2) {
        int num = deque.isEmpty() ? 0 : deque.peekFirst();
        if (num > 0 && num2 < 0) {
            int eliminate = eliminate(deque.pop(), num2);
            if (eliminate > 0) {
                deque.push(eliminate);
            } else if (eliminate < 0) {
                recursion(deque, num2);
            }
        } else deque.push(num2);
    }

    public int eliminate(int num1, int num2) {
        int result = Math.abs(num1) - Math.abs(num2);
        if (result == 0) {
            return 0;
        } else if (result > 0) return num1;
        else return num2;
    }

    public int[] dailyTemperature1s(int[] temperatures) {
        int len = temperatures.length;
        int[] ints = new int[len];
        ints[len - 1] = 0;
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (temperatures[j] > temperatures[i]) ints[i] = j - i;
                break;
            }
        }
        return ints;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> deque = new LinkedList<>();
        int[] ints = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!deque.isEmpty() && temperatures[deque.peek()] < temperatures[i]) {
                int n = deque.pop();
                ints[n] = i - n;
            }
            deque.push(i);
        }
        return ints;
    }


    public int largestRectangleArea(int[] heights) {
        Deque<Integer> deque = new LinkedList<>();
        int maxArea = 0;
        int len = heights.length;
        for (int i = 0; i < heights.length; i++) {
            while (!deque.isEmpty() && heights[deque.peek()] > heights[i]) {
                int high = heights[deque.pop()];
                int w = deque.isEmpty() ? i : i - deque.peek() - 1;
                maxArea = Math.max(maxArea, high * w);
            }
            deque.push(i);
        }
        while (!deque.isEmpty()) {
            int high = heights[deque.pop()];
            int w = deque.isEmpty() ? 1 : len - deque.peek() - 1;
            maxArea = Math.max(maxArea, high * w);
        }
        return maxArea;
    }

    public int maximalRectangle(String[] matrix) {

        int len1 = matrix.length;
        if (len1 == 0) return 0;
        int len2 = matrix[0].length();

        int[][] high = new int[len1 + 1][len2 + 1];
        int maxArea = 0;
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                high[i][j] = matrix[i - 1].charAt(j - 1) == '1' ? high[i - 1][j] + 1 : 0;
                int minHigh = high[i][j];
                for (int k = j; k >= 0 && high[i][k] != 0; k--) {
                    minHigh = Math.min(minHigh, high[i][k]);
                    maxArea = Math.max(maxArea, minHigh * (j - k + 1));
                }
            }
        }
        return maxArea;

    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
//        treeNode2.left = treeNode4;
//        treeNode2.right = treeNode5;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        offer offer = new offer();
        String serialize = offer.serialize(treeNode1);
        System.out.println(serialize);
//        CBTInserter C = new CBTInserter(treeNode1);
//        C.insert(7);
//        C.insert(8);
//        List<Integer> list=new ArrayList<>();
//        list.set()
    }

    static class CBTInserter {

        TreeNode root;
        Deque<TreeNode> deque;

        public CBTInserter(TreeNode root) {
            this.deque = new ArrayDeque<>();
            this.root = root;
            Deque<TreeNode> deque1 = new ArrayDeque<>();
            deque1.push(root);
            while (!deque1.isEmpty()) {
                TreeNode poll = deque1.pollLast();
                if (poll.left != null) {
                    deque1.push(poll.left);
                }
                if (poll.right != null) {
                    deque1.push((poll.right));
                }
                if (poll.left == null || poll.right == null) {
                    deque.push(poll);
                }

            }
        }

        public int insert(int v) {
            TreeNode treeNode1 = new TreeNode(v);
            TreeNode treeNode = deque.peekLast();
            int res = treeNode.val;
            if (treeNode.left == null) {
                treeNode.left = treeNode1;
            } else if (treeNode.right == null) {
                treeNode.right = treeNode1;
                deque.pollLast();
            }
            deque.push(treeNode1);
            return res;
        }

        public TreeNode get_root() {
            return root;
        }
    }

    public List<Integer> largestValues1(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(list, 0, root);
        return list;
    }

    void dfs(List<Integer> list, int high, TreeNode treeNode) {
        if (list.size() == high) {
            list.add(treeNode.val);
        } else list.set(high, Math.max(list.get(high), treeNode.val));

        if (treeNode.left != null) {
            dfs(list, high + 1, treeNode.left);
        }
        if (treeNode.right != null) {
            dfs(list, high + 1, treeNode.right);
        }
    }

    public List<Integer> largestValues(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int max = Integer.MIN_VALUE;
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode treeNode = deque.poll();
                max = Math.max(max, treeNode.val);
                if (treeNode.left != null) {
                    deque.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    deque.add(treeNode.right);
                }
            }
            list.add(max);
        }

        return list;
    }

    int high1 = 0;
    int leftSum = 0;

    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 0);
        return leftSum;
    }

    void dfs(TreeNode treeNode, int high) {
        if (treeNode.left == null || treeNode.right == null) return;
        high++;
        dfs(treeNode.left, high);
        dfs(treeNode.right, high);
        if (high > high1) {
            high1 = high;
            leftSum = treeNode.val;
        }
    }

    int getHigh1 = 0;


    public List<Integer> rightSideView1(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        dfs1(root, list, 0);
        return list;
    }

    void dfs1(TreeNode treeNode, List<Integer> list, int high1) {
        if (treeNode == null) return;
        high1++;
        if (high1 > getHigh1) {
            getHigh1 = high1;
            list.add(treeNode.val);
        }
        dfs1(treeNode.right, list, high1);
        dfs1(treeNode.left, list, high1);
    }

    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            int rightSum = 0;
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode treeNode = deque.poll();
                rightSum = treeNode.val;
                if (treeNode.left != null) {
                    deque.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    deque.add(treeNode.right);
                }
            }
            list.add(rightSum);
        }

        return list;
    }

    public TreeNode pruneTree(TreeNode root) {
        boolean dfs = dfs(root);
        if (!dfs) return null;
        return root;
    }

    boolean dfs(TreeNode treeNode) {
        if (treeNode == null) return false;

        boolean dfsLeft = dfs(treeNode.left);
        boolean dfsRight = dfs(treeNode.right);
        if (!dfsRight && !dfsLeft && treeNode.val == 0) {
            return false;
        }
        if (!dfsLeft) {
            treeNode.left = null;
        }
        if (!dfsRight) {
            treeNode.right = null;
        }
        return true;
    }


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder stringBuilder = new StringBuilder();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.val != Integer.MIN_VALUE) {
                    stringBuilder.append(poll.val).append(",");
                } else {
                    stringBuilder.append("null").append(",");
                    continue;
                }
                if (poll.left != null) {
                    queue.add(poll.left);
                } else queue.add(new TreeNode(Integer.MIN_VALUE));
                if (poll.right != null) {
                    queue.add(poll.right);
                } else queue.add(new TreeNode(Integer.MIN_VALUE));
            }
        }
        return stringBuilder.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == "") return null;
        String[] split = data.split(",");
        Queue<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(Integer.valueOf(split[0]));
        queue.add(root);
        for (int i = 1; i < split.length && !queue.isEmpty(); ) {
            TreeNode poll = queue.poll();
            if (poll.left == null && !split[i].equals("null")) {
                TreeNode treeNode = new TreeNode(Integer.valueOf(split[i]));
                poll.left = treeNode;
                queue.add(treeNode);
            }
            i++;
            if (poll.right == null && !split[i].equals("null")) {
                TreeNode treeNode = new TreeNode(Integer.valueOf(split[i]));
                poll.right = treeNode;
                queue.add(treeNode);
            }
            i++;
        }
        return root;

    }
//    public TreeNode deserialize(String data) {
//        if(data.length() == 0) return null; // 特判：data == ""
//        String[] nodes = data.split(",");
//        Queue<TreeNode> q = new ArrayDeque<>();
//        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
//        q.add(root);
//        int idx = 1, n = nodes.length;
//        while(idx < n){ // 不必以!q.isEmpty()作为判断条件
//            TreeNode head = q.remove();
//            if(!nodes[idx].equals("null")){
//                TreeNode left = new TreeNode(Integer.parseInt(nodes[idx]));
//                head.left = left; // left挂接到head
//                q.add(left);
//            }
//            idx++;
//            if(idx < n && !nodes[idx].equals("null")){
//                TreeNode right = new TreeNode(Integer.parseInt(nodes[idx]));
//                head.right = right; // right挂接到head
//                q.add(right);
//            }
//            idx++;
//        }
//        return root;
//    }

    // Decodes your encoded data to tree.\


//    public TreeNode appendTree(Queue<String> queue) {
//        String poll = queue.poll();
//        if (poll.equals("null")) {
//            return null;
//        }
//        TreeNode root = new TreeNode(Integer.valueOf(poll));
//        root.left = appendTree(queue);
//        root.right = appendTree(queue);
//        return root;
//    }

    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        dfs5(root, 0);
        return sums;
    }

    int sums = 0;

    void dfs5(TreeNode treeNode, int a) {
        int c = a * 10 + treeNode.val;
        if (treeNode.right == null && treeNode.left == null) {
            sums = sums + c;
            return;
        }
        if (treeNode.left != null)
            dfs5(treeNode.left, c);
        if (treeNode.right != null)
            dfs5(treeNode.right, c);
    }

    public int pathSum1(TreeNode root, int targetSum) {
        dfs6(root, targetSum);
        return sum;
    }

    int sum = 0;

    void dfs6(TreeNode treeNode, int targetSum) {
        if (treeNode == null) return;
        check(treeNode, targetSum, 0);
        dfs6(treeNode.left, targetSum);
        dfs6(treeNode.right, targetSum);
    }

    void check(TreeNode treeNode, int targetSum, int sums) {
        if (treeNode == null) return;
        int a = treeNode.val + sums;
        if (a == targetSum) sum++;
        check(treeNode.left, targetSum, a);
        check(treeNode.right, targetSum, a);
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}